package pratice.sorting;

import org.junit.After;
import org.junit.Before;
import org.junit.Test;

/**
 * 排序算法
 *
 * @author 吴宇亮 on 2019/2/27 9:45
 */
public class sorting {

    int[] array;

    @Before
    public void before(){
        array = new int[]{10, 20, 15, 0, 6, 7, 2, 1, -5, 55};
    }

    @After
    public void after(){
        for(int i = 0; i < array.length; i++){
            System.out.println(array[i]);
        }
    }

    /**
     * 冒泡排序
     * 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
     * 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
     * 针对所有的元素重复以上的步骤，除了最后一个。
     * 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
     */
    @Test
    public void bubbleSort(){
        int temp = 0;
        //注意，一定要i < array.length - 1，否则到最后一个跟后一个比的时候就会数组越界了
        for(int i = 0; i < array.length - 1; i++){//因为前一个和后一个比，所以最后一个不用比
            for(int j = 0; j < array.length - 1 - i; j++ ){//第二次循环是比还没有被排序的，已经排完序是后i个
                if(array[j + 1] < array[j]){//如果后一个比前一个小，小的就冒泡上去
                    temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                }
            }
        }
    }

    /**
     * 快速排序
     */
    @Test
    public void quick()
    {
        if(array.length > 0)   //查看数组是否为空
        {
            quickSort(array, 0, array.length-1);
        }
    }

    /**
     *
     * @param numbers 带排序数组
     * @param low  开始位置
     * @param high 结束位置
     */
    public static void quickSort(int[] numbers, int low, int high)
    {
        if(low < high)
        {
            int middle = getMiddle(numbers,low,high); //将numbers数组进行一分为二
            quickSort(numbers, low, middle-1);   //对低字段表进行递归排序
            quickSort(numbers, middle+1, high); //对高字段表进行递归排序
        }
    }

    /**
     * 查找出中轴（默认是最低位low）的在numbers数组排序后所在位置
     *
     * @param numbers 带查找数组
     * @param low   开始位置
     * @param high  结束位置
     * @return  中轴所在位置
     */
    public static int getMiddle(int[] numbers, int low, int high)
    {
        int temp = numbers[low]; //数组的第一个作为中轴
        while(low < high)
        {
            while(low < high && numbers[high] > temp)
            {
                high--;
            }
            numbers[low] = numbers[high]; //比中轴小的记录移到低端
            while(low < high && numbers[low] < temp)
            {
                low++;
            }
            numbers[high] = numbers[low] ; //比中轴大的记录移到高端
        }
        numbers[low] = temp ; //中轴记录到尾
        return low ; // 返回中轴的位置
    }


}
